{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Side Length of a Square with Sum Less than or Equal to Threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSideLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #元素和小于等于阈值的正方形的最大边长"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为&nbsp;<code>m x n</code>&nbsp;的矩阵&nbsp;<code>mat</code>&nbsp;和一个整数阈值&nbsp;<code>threshold</code>。</p>\n",
    "\n",
    "<p>请你返回元素总和小于或等于阈值的正方形区域的最大边长；如果没有这样的正方形区域，则返回 <strong>0&nbsp;</strong>。<br />\n",
    "&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/12/15/e1.png\" style=\"height: 186px; width: 335px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>总和小于或等于 4 的正方形的最大边长为 2，如图所示。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]], threshold = 1\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 300</code></li>\n",
    "\t<li><code>0 &lt;= mat[i][j] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= threshold &lt;= 10<sup>5</sup></code><sup>&nbsp;</sup></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold](https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold](https://leetcode.cn/problems/maximum-side-length-of-a-square-with-sum-less-than-or-equal-to-threshold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]]\\n4', '[[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2],[2,2,2,2,2]]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        for i in range(m):\n",
    "            mat[i].insert(0,0)\n",
    "        mat = [[0 for _ in range(n+1)]] + mat\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat[i][j] = mat[i-1][j]+mat[i][j-1]-mat[i-1][j-1]+mat[i][j]\n",
    "        for k in range(min(m,n),0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    if(mat[i+k-1][j+k-1]-mat[i-1][j+k-1]-mat[i+k-1][j-1]+mat[i-1][j-1]<=threshold):\n",
    "                        return k\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]\n",
    "        \n",
    "        r, ans = min(m, n), 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                for c in range(ans + 1, r + 1):\n",
    "                    if i + c - 1 <= m and j + c - 1 <= n and getRect(i, j, i + c - 1, j + c - 1) <= threshold:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        res = mx = 0\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        pres = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pres[i + 1][j + 1] = pres[i][j + 1] + pres[i + 1][j] - pres[i][j] + mat[i][j]\n",
    "\n",
    "        # 暴力优化超时... 2.7x10^7\n",
    "        # for i in range(n):\n",
    "        #     for j in range(m):\n",
    "        #         if n - i <= res:\n",
    "        #             return res\n",
    "        #         if m - j <= res:\n",
    "        #             break\n",
    "        #         for k in range(min(n, m), res, -1):\n",
    "        #             x, y = i + k - 1, j + k - 1\n",
    "        #             if 0 <= x < n and 0 <= y < m:\n",
    "        #                 s = pres[x + 1][y + 1] - pres[i][j]\n",
    "        #                 s -= pres[i][y + 1] - pres[i][j]\n",
    "        #                 s -= pres[x + 1][j] - pres[i][j]\n",
    "        #                 if s <= threshold:\n",
    "        #                     res = max(res, k)\n",
    "        #                     break\n",
    "\n",
    "        l, r = 0, min(n, m)\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            match = False\n",
    "            k = mid\n",
    "            for i in range(n):\n",
    "                for j in range(m):\n",
    "                    x, y = i + k - 1, j + k - 1\n",
    "                    if 0 <= x < n and 0 <= y < m:\n",
    "                        s = pres[x + 1][y + 1] - pres[i][j]\n",
    "                        s -= pres[i][y + 1] - pres[i][j]\n",
    "                        s -= pres[x + 1][j] - pres[i][j]\n",
    "                        if s <= threshold:\n",
    "                            match = True\n",
    "                            break\n",
    "\n",
    "            if match:\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        p = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # 二维前缀和 的正方形\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + mat[i-1][j-1]\n",
    "        # print(p)\n",
    "        \n",
    "        def get(x1, y1, x2, y2):\n",
    "            return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1]\n",
    "\n",
    "        l, r = 0, min(m, n) + 1\n",
    "        # ans = 0\n",
    "        while l + 1 < r:\n",
    "            mid = (l + r) // 2\n",
    "            find = any(get(i, j, i + mid -1, j+mid-1) <= threshold for i in range(1, m-mid+2) for j in range(1, n-mid+2))\n",
    "            if find:\n",
    "                # ans = mid\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "\n",
    "        mat_sum =[[0]*(len(mat[0])+1) for _ in range(len(mat)+1)]\n",
    "        min_s =float('inf')\n",
    "        for i in range(1,len(mat)+1):\n",
    "            for j in range(1,len(mat[0])+1):\n",
    "                if mat[i-1][j-1] < min_s:\n",
    "                    min_s=mat[i-1][j-1]\n",
    "                mat_sum[i][j] = mat_sum[i-1][j]+mat_sum[i][j-1] - mat_sum[i-1][j-1] +mat[i-1][j-1]\n",
    "        if min_s>threshold:\n",
    "            return 0\n",
    "        max_length =min(len(mat),len(mat[0]))\n",
    "        for length  in range(max_length,1,-1):\n",
    "            for start0 in range(len(mat_sum)-length):\n",
    "                for start1 in range (len(mat_sum[0])-length):\n",
    "                    end0 =start0+length\n",
    "                    end1 =start1+length\n",
    "\n",
    "                    area = mat_sum[end0][end1]- mat_sum[end0][start1]-mat_sum[start0][end1]+\\\n",
    "                    mat_sum[start0][start1]\n",
    "                    if area<=threshold:\n",
    "                        return length\n",
    "\n",
    "        if min_s<=threshold:\n",
    "            return 1\n",
    "        # else :\n",
    "        #     return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        matrix = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                matrix[i + 1][j + 1] = mat[i][j] + matrix[i + 1][j] + matrix[i][j + 1] - matrix[i][j]\n",
    "        left = 0\n",
    "        right = min(m, n)\n",
    "        while left <= right:\n",
    "            edge = (left + right) // 2\n",
    "            if any(matrix[i + edge][j + edge] + matrix[i][j] - matrix[i][j + edge] - matrix[i + edge][j] <=                     threshold for i in range(m - edge + 1) for j in range(n - edge + 1)):\n",
    "                left = edge + 1\n",
    "            else:\n",
    "                right = edge - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def check(self, pre_sum, k, threshold):\r\n",
    "        m, n = len(pre_sum), len(pre_sum[0])\r\n",
    "        for i in range(k, m):\r\n",
    "            if pre_sum[i][k] - pre_sum[i - k][k] <= threshold:\r\n",
    "                return True\r\n",
    "            for j in range(k, n):\r\n",
    "                if pre_sum[i][j] - pre_sum[i - k][j] - pre_sum[i][j - k] + pre_sum[i - k][j - k] <= threshold:\r\n",
    "                    return True\r\n",
    "        return False\r\n",
    "    def maxSideLength(self, mat: list[list[int]], threshold: int) -> int:\r\n",
    "        # 求二位前缀和\r\n",
    "        m, n = len(mat), len(mat[0])\r\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + mat[i][j]\r\n",
    "        # 二分查找\r\n",
    "        left, right = 0, min(m, n)\r\n",
    "        while left < right:\r\n",
    "            mid = (left + right + 1) // 2\r\n",
    "            if self.check(pre_sum, mid, threshold):\r\n",
    "                left = mid\r\n",
    "            else:\r\n",
    "                right = mid - 1\r\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]\n",
    "        \n",
    "        l, r, res = 1, min(m, n), 0\n",
    "\n",
    "        while l <= r:\n",
    "\n",
    "            mid = ( l + r ) // 2\n",
    "\n",
    "            find = any(getRect(i, j, i + mid - 1, j + mid - 1) <= threshold for i in range(1, m - mid + 2) for j in range(1, n - mid + 2))\n",
    "\n",
    "            if find:\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[0] * (c + 1) for _ in range(r + 1)]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(r - 1, -1, -1):\n",
    "            for j in range(c - 1, -1, -1):\n",
    "                for k in range(res + 1, min(i + 1, j + 1) + 1):\n",
    "                # for k in range(1, min(i + 1, j + 1) + 1):\n",
    "                # for k in range(min(i + 1, j + 1), 0, -1):\n",
    "   \n",
    "                    top_x, left_y = i - k + 1, j - k + 1\n",
    "                    lower_x, right_y = i, j\n",
    "\n",
    "                    val = dp[lower_x + 1][right_y + 1] - (dp[lower_x + 1][left_y] + dp[top_x][right_y + 1] - dp[top_x][left_y])\n",
    "\n",
    "                    cond = val <= threshold\n",
    "                    if cond:\n",
    "                        res = max(res, k)\n",
    "                    else:\n",
    "                        break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        dp[0][0] = mat[0][0]\n",
    "        ans = float('-inf')\n",
    "        for i in range(m):\n",
    "            if mat[i][0] == threshold:\n",
    "                ans = 1\n",
    "            dp[i][0] = dp[i-1][0] + mat[i][0]\n",
    "        for i in range(n):\n",
    "            if mat[0][i] == threshold:\n",
    "                ans = 1\n",
    "            dp[0][i] = dp[0][i-1] + mat[0][i-1]\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i][j]\n",
    "                if mat[i][j] == threshold:\n",
    "                    ans = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for d in range(2, min(i, j) + 2):\n",
    "                    nn, mm = i - d, j - d\n",
    "                    if nn < 0 and mm < 0:\n",
    "                        if dp[i][j] <= threshold:\n",
    "                            ans = max(ans, d)\n",
    "                        continue\n",
    "                    elif nn < 0:\n",
    "                        sums = dp[i][j] - dp[i][j - d]\n",
    "                    elif mm < 0:\n",
    "                        sums = dp[i][j] - dp[i - d][j]\n",
    "                    else:\n",
    "                        sums = dp[i][j] - dp[i - d][j] - dp[i][j - d] + dp[i - d][j - d]\n",
    "                    if sums <= threshold:\n",
    "                        ans = max(ans, d)\n",
    "        if ans == float('-inf'):\n",
    "            return 0\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinarySearch:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_left(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠左满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_int_right(low: int, high: int, check: Callable) -> int:\n",
    "        # 模板: 整数范围内二分查找，选择最靠右满足check\n",
    "        while low < high - 1:\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_left(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠左满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                high = mid\n",
    "            else:\n",
    "                low = mid\n",
    "        return low if check(low) else high\n",
    "\n",
    "    @staticmethod\n",
    "    def find_float_right(low: float, high: float, check: Callable, error=1e-6) -> float:\n",
    "        # 模板: 浮点数范围内二分查找, 选择最靠右满足check\n",
    "        while low < high - error:\n",
    "            mid = low + (high - low) / 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n",
    "\n",
    "class PreFixSumMatrix:\n",
    "    def __init__(self, mat):\n",
    "        self.mat = mat\n",
    "        # 二维前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        self.pre = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.pre[i + 1][j + 1] = self.pre[i][j + 1] + \\\n",
    "                    self.pre[i + 1][j] - self.pre[i][j] + mat[i][j]\n",
    "\n",
    "    def query(self, xa, ya, xb, yb):\n",
    "        # 二维子矩阵和查询，索引从 0 开始，左上角 [xa, ya] 右下角 [xb, yb]\n",
    "        return self.pre[xb + 1][yb + 1] - self.pre[xb +\n",
    "                                                   1][ya] - self.pre[xa][yb + 1] + self.pre[xa][ya]\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        pre = PreFixSumMatrix(mat)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        \n",
    "        def check(x):\n",
    "            if not x:\n",
    "                return True\n",
    "            for i in range(x-1, m):\n",
    "                for j in range(x-1, n):\n",
    "                    if pre.query(i-x+1, j-x+1, i, j) <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        return BinarySearch().find_int_right(0, m if m < n else n, check)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        def check(k):\n",
    "            for i in range(n-k+1):\n",
    "                for j in range(m-k+1):\n",
    "                    if prefix[i+k][j+k]-prefix[i+k][j]-prefix[i][j+k]+prefix[i][j]<=threshold: return True\n",
    "            return False\n",
    "\n",
    "        n,m=len(mat),len(mat[0])\n",
    "        prefix=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                prefix[i+1][j+1]=prefix[i+1][j]+prefix[i][j+1]-prefix[i][j]+mat[i][j]\n",
    "\n",
    "        l,r=0,min(n,m)\n",
    "        while l<r:\n",
    "            mid=(l+r+1)>>1\n",
    "            if not check(mid): r=mid-1\n",
    "            else: l=mid\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "\n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        l, r, res = 1, min(m, n), 0\n",
    "\n",
    "        while l <= r:\n",
    "\n",
    "            mid = ( l + r ) // 2\n",
    "\n",
    "            find = any(getRect(i, j, i + mid - 1, j + mid - 1) <= threshold for i in range(1, m - mid + 2) for j in range(1, n - mid + 2))\n",
    "\n",
    "            if find:\n",
    "                res = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j] + mat[i][j]\n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return pre_sum[x2 + 1][y2 + 1] - pre_sum[x1][y2 + 1] - pre_sum[x2 + 1][y1] + pre_sum[x1][y1]\n",
    "        l, r, ans = 1, min(m, n), 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            state = 0\n",
    "            for i in range(m - mid + 1):\n",
    "                if state == 1: break\n",
    "                down_i = i + mid - 1\n",
    "                for j in range(n - mid + 1):\n",
    "                    if state == 1: break\n",
    "                    right_j = j + mid - 1\n",
    "                    if getRect(i, j, down_i, right_j) <= threshold:\n",
    "                        state = 1\n",
    "            if state:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0]*(n+1) for _ in range(m+1)]\n",
    "        lower = float('inf')\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i+1][j+1] = dp[i][j+1]+dp[i+1][j]-dp[i][j]+mat[i][j]\n",
    "                if mat[i][j] < lower:\n",
    "                    lower = mat[i][j]\n",
    "        if lower > threshold:\n",
    "            return 0\n",
    "\n",
    "        def check(num):\n",
    "            for i in range(m-num+1):\n",
    "                for j in range(n-num+1):\n",
    "                    cur = dp[i+num][j+num] - dp[i+num][j] - dp[i][j+num] + dp[i][j]\n",
    "                    if cur <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        low = 1\n",
    "        high = m if m>n else n\n",
    "        while low < high-1:\n",
    "            mid = low+(high-low)//2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return high if check(high) else low\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "\n",
    "        mat_sum =[[0]*(len(mat[0])+1) for _ in range(len(mat)+1)]\n",
    "        for i in range(1,len(mat)+1):\n",
    "            for j in range(1,len(mat[0])+1):\n",
    "                mat_sum[i][j] = mat_sum[i-1][j]+mat_sum[i][j-1] - mat_sum[i-1][j-1] +mat[i-1][j-1]\n",
    "\n",
    "        max_length =min(len(mat),len(mat[0]))\n",
    "        for length  in range(max_length,1,-1):\n",
    "            for start0 in range(len(mat_sum)-length):\n",
    "                for start1 in range (len(mat_sum[0])-length):\n",
    "                    end0 =start0+length\n",
    "                    end1 =start1+length\n",
    "\n",
    "                    area = mat_sum[end0][end1]- mat_sum[end0][start1]-mat_sum[start0][end1]+\\\n",
    "                    mat_sum[start0][start1]\n",
    "                    if area<=threshold:\n",
    "                        return length\n",
    "        \n",
    "        if min(min(mat))>threshold:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pref_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pref_sum[i][j] = pref_sum[i-1][j] + pref_sum[i][j-1] - pref_sum[i-1][j-1] + mat[i-1][j-1]\n",
    "        for d in range(min(m, n), 0, -1):\n",
    "            for i in range(m - d + 1):\n",
    "                for j in range(n - d + 1):\n",
    "                    if pref_sum[i+d][j+d] - pref_sum[i][j+d] - pref_sum[i+d][j] + pref_sum[i][j] <= threshold:\n",
    "                        return d\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        # 查找的正方形的边长越长，其计算出来的元素总和越大。我们可以二分正方形的边长，在满足阈值条件下尽可能地扩大正方形的边长，其等价于在升序数组中查找一个小于等于 k 的最大元素。\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dp =[[0 for i in range(n + 1)] for j in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                # 计算prefix sum用来后续快速计算区域内元素总和。注意prefix sum公式，多加的一部分需要去掉。\n",
    "                dp[i][j] = mat[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]\n",
    "        \n",
    "        left = 0  # 最小边长\n",
    "        right = min(m, n)  # 最大边长\n",
    "        while left < right:\n",
    "            # 划分 [left, mid - 1] 与 [mid, right] ，mid 被分到右边，对应 mid = left + (right - left + 1) // 2\n",
    "            mid = left + (right - left + 1) // 2\n",
    "            \n",
    "            if self.is_square_threshold(m, n, dp, mid, threshold):\n",
    "                # 当前mid能满足threshold要求，说明left设置的太小了，下一轮搜索[mid, right]\n",
    "                left = mid\n",
    "            else:\n",
    "                # 当前mid不能满足threshold要求，说明right设置的太大了，下一轮搜索[left, mid - 1]\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "    def is_square_threshold(self, m, n, dp, k, threshold):\n",
    "        # 这个helper method计算的是，以dp[i][j] 为右下角，k为边长的正方形的区域内元素总和是否小于等于threshold（即满足题目要求）\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                if i - k < 0 or j - k < 0:\n",
    "                    continue\n",
    "                if dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k] <= threshold:\n",
    "                    return True\n",
    "        return False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        # 预处理g\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        g = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                g[i][j] = g[i-1][j]+g[i][j-1]-g[i-1][j-1]+mat[i-1][j-1]\n",
    "        # 优化\n",
    "        def area(x1,y1,x2,y2):\n",
    "            return g[x2][y2]+g[x1-1][y1-1]-g[x1-1][y2]-g[x2][y1-1]\n",
    "        # 枚举正方形左上角\n",
    "        ans = 0\n",
    "        k = min(m,n)\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                for length in range(ans+1,k+1):\n",
    "                    if i+length-1<=m and j+length-1<=n and area(i,j,i+length-1,j+length-1) <= threshold:\n",
    "                        ans = length\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        presum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i + 1][j + 1] = presum[i][j + 1] + presum[i + 1][j] - presum[i][j] + mat[i][j]\n",
    "                l = min(i + 1, j + 1)\n",
    "                # 左上角(i - l + 1, j - l + 1) 右下角(i, j)\n",
    "                while presum[i + 1][j + 1] - presum[i + 1][j - l + 1] - presum[i - l + 1][j + 1] + presum[i - l + 1][j - l + 1] > threshold:\n",
    "                    l -= 1\n",
    "                res = max(res, l)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        rowSize = len(mat)\n",
    "        columnSize = len(mat[0])\n",
    "        P = [[0]*(columnSize + 1) for i in range(0, rowSize + 1)]\n",
    "        for i in range(0, rowSize + 1):\n",
    "            for j in range(0, columnSize + 1):\n",
    "                if i == 0 or j == 0:\n",
    "                    P[i][j] = 0\n",
    "                else:\n",
    "                    P[i][j] = P[i-1][j] + P[i][j-1] + mat[i-1][j-1] - P[i-1][j-1]\n",
    "\n",
    "        # 正方形大小\n",
    "        maxSquareSize = min(rowSize, columnSize)\n",
    "        minSquareSize = 1\n",
    "        # 当前正方形大小\n",
    "        square = round(maxSquareSize / 2)\n",
    "        result = 0\n",
    "        while square > 0 and square <= maxSquareSize:\n",
    "            re = 0\n",
    "            for i in range(0, rowSize - square + 1):\n",
    "                exit = False\n",
    "                for j in range(0, columnSize - square + 1):\n",
    "                    sum = P[i+square][j+square] - P[i][j+square] - P[i+square][j] + P[i][j]\n",
    "                    if sum <= threshold:\n",
    "                        re = square\n",
    "                        exit = True\n",
    "                        break\n",
    "                if exit:\n",
    "                    break\n",
    "            if re > 0:\n",
    "                result = re\n",
    "                minSquareSize = square + 1\n",
    "            else:\n",
    "                maxSquareSize = square - 1\n",
    "            square = math.floor((minSquareSize + maxSquareSize) / 2)\n",
    "            if minSquareSize > maxSquareSize or maxSquareSize == 0:\n",
    "                break\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        k0 = min(m,n)\n",
    "        mat0 = [[0 for j in range(n+1)] for i in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat0[i][j] = mat0[i-1][j]+mat0[i][j-1]-mat0[i-1][j-1]+mat[i-1][j-1]\n",
    "        for k in range(k0,0,-1):\n",
    "            for i in range(1,m-k+2):\n",
    "                for j in range(1,n-k+2):\n",
    "                    t = mat0[i+k-1][j+k-1]-mat0[i-1][j+k-1]-mat0[i+k-1][j-1]+mat0[i-1][j-1]\n",
    "                    #print(i,j,k,t)\n",
    "                    if(t<=threshold):\n",
    "                        return k\n",
    "        #for i in range(m):\n",
    "            #for j in range(n):\n",
    "                #if(mat[i][j]<=threshold):\n",
    "\n",
    "\n",
    "\n",
    "                    #return 1\n",
    "        \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i][j + 1] + pre_sum[i + 1][j] - pre_sum[i][j] + mat[i][j]\n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return pre_sum[x2 + 1][y2 + 1] - pre_sum[x1][y2 + 1] - pre_sum[x2 + 1][y1] + pre_sum[x1][y1]\n",
    "        l, r, ans = 1, min(m, n), 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            state = any(getRect(i, j, i + mid - 1, j + mid - 1) <= threshold for j in range(n - mid + 1) for i in range(m - mid + 1))\n",
    "            if state:\n",
    "                ans = mid\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat, threshold):\n",
    "        \"\"\"\n",
    "        求解矩形之中不超过threshold的最大的正方形边长\n",
    "        Args:\n",
    "            mat (list[list[int]]): 原始矩形\n",
    "            threashold (int): 阈值\n",
    "        returns (int): 最大的正方形的边长\n",
    "        \"\"\"\n",
    "        #处理异常情况\n",
    "        if mat == None or threshold == None:\n",
    "            return 0 \n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        p = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        #求解二维前缀数组, p[i][j]表示从左上角(1, 1)到(i, j)所构成的矩形的元素和\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                p[i][j] = p[i - 1][j] + p[i][j - 1] + mat[i - 1][j - 1] - p[i - 1][j - 1]\n",
    "        \n",
    "        #使用二分查找最大的符合要求的边长\n",
    "        left, right, ans = 1, min(m, n), 0\n",
    "\n",
    "        while left <= right:\n",
    "            mid = left + ((right - left) >> 1)\n",
    "\n",
    "            #枚举mat之中所有边长为mid的正方形, 查看是否有符合条件的\n",
    "            flag = False \n",
    "            for i in range(1, m + 1):\n",
    "                for j in range(1, n + 1):\n",
    "                    #若不越界\n",
    "                    if i + mid - 1 <= m and j + mid - 1 <= n:\n",
    "                        if self.getRecArea(p, i, j, i + mid - 1, j + mid - 1) <= threshold:\n",
    "                            flag = True \n",
    "                            ans = mid \n",
    "            \n",
    "            #若未找到, 尝试减小边长\n",
    "            if flag == False:\n",
    "                right = mid - 1\n",
    "                        \n",
    "            #若找到了, 尝试增加边长\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        \n",
    "        return ans \n",
    "\n",
    "    def getRecArea(self, p, r1, c1, r2, c2):\n",
    "        \"\"\"\n",
    "        求解任意矩形框的元素和\n",
    "        Args:\n",
    "            r1 (int): 左上角行索引\n",
    "            c1 (int): 左上角列索引\n",
    "            r2 (int): 右下角行索引\n",
    "            c2 (int): 右下角列索引\n",
    "        returns (int): 该矩形框的元素和\n",
    "        \"\"\"\n",
    "        return p[r2][c2] - p[r2][c1 - 1] - p[r1 - 1][c2] + p[r1 - 1][c1 - 1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "\n",
    "        mat_sum =[[0]*(len(mat[0])+1) for _ in range(len(mat)+1)]\n",
    "        for i in range(1,len(mat)+1):\n",
    "            for j in range(1,len(mat[0])+1):\n",
    "                mat_sum[i][j] = mat_sum[i-1][j]+mat_sum[i][j-1] - mat_sum[i-1][j-1] +mat[i-1][j-1]\n",
    "\n",
    "        max_length =min(len(mat),len(mat[0]))\n",
    "        for length  in range(max_length,1,-1):\n",
    "            for start0 in range(len(mat_sum)-length):\n",
    "                for start1 in range (len(mat_sum[0])-length):\n",
    "                    end0 =start0+length\n",
    "                    end1 =start1+length\n",
    "\n",
    "                    area = mat_sum[end0][end1]- mat_sum[end0][start1]-mat_sum[start0][end1]+\\\n",
    "                    mat_sum[start0][start1]\n",
    "                    if area<=threshold:\n",
    "                        return length\n",
    "        \n",
    "        if min(min(mat))>threshold:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        r, c = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[0] * (c + 1) for _ in range(r + 1)]\n",
    "\n",
    "        for i in range(1, len(dp)):\n",
    "            for j in range(1, len(dp[0])):\n",
    "                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        res = 0\n",
    "\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                # for k in range(1, min(i + 1, j + 1) + 1):\n",
    "                for k in range(min(i + 1, j + 1), 0, -1):\n",
    "                    if k <= res:\n",
    "                        break\n",
    "                    top_x, left_y = i - k + 1, j - k + 1\n",
    "                    lower_x, right_y = i, j\n",
    "\n",
    "                    val = dp[lower_x + 1][right_y + 1] - (dp[lower_x + 1][left_y] + dp[top_x][right_y + 1] - dp[top_x][left_y])\n",
    "\n",
    "                    cond = val <= threshold\n",
    "                    if cond:\n",
    "                        res = max(res, k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        flag = True\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if mat[i-1][j-1] <= threshold:\n",
    "                    flag = False\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i-1][j-1]\n",
    "        if flag:\n",
    "            return 0\n",
    "        \n",
    "        # for row in dp:\n",
    "        #     print(row)\n",
    "        ans = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                x, y = i - ans, j - ans\n",
    "                temp = ans\n",
    "                # print(i, j,' --')\n",
    "                while  x >= 0 and y >= 0 and dp[i][j] - dp[x][j] - dp[i][y] + dp[x][y] <= threshold:\n",
    "                    ans = max(temp, ans)\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                    temp += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        p = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + mat[i-1][j-1]\n",
    "        \n",
    "        def getm(x1, y1, x2, y2):\n",
    "            return p[x2][y2] - p[x1-1][y2] - p[x2][y1-1] + p[x1-1][y1-1]\n",
    "        \n",
    "        def check(mid):\n",
    "            for i in range(1, m - mid + 2):\n",
    "                for j in range(1, n - mid + 2):\n",
    "                    if getm(i, j, i + mid - 1, j + mid - 1) <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        l, r, ans = 1, min(m,n), 0\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid -1 \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        sum = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for row,mat_row in enumerate(mat):\n",
    "            for col,value in enumerate(mat_row):\n",
    "                sum[row+1][col+1]=sum[row][col+1]+sum[row+1][col]-sum[row][col]+value\n",
    "        result=0\n",
    "        for row in range(1,m+1):\n",
    "            for col in range(1,n+1):\n",
    "                while row+result<=m and col+result<=n:\n",
    "                    value=self.get_rect(sum,row,col,row+result,col+result)\n",
    "                    if value<=threshold:\n",
    "                        result+=1\n",
    "                    else:\n",
    "                        break\n",
    "        return result\n",
    "\n",
    "    def get_rect(self,sum:List[List[int]],x1:int,y1:int,x2:int,y2:int)->int:\n",
    "        return sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        presum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i+1][j+1] = presum[i][j+1] + presum[i+1][j] - presum[i][j] + mat[i][j]\n",
    "                l = min(i+1, j+1)\n",
    "                while presum[i+1][j+1] - presum[i-l+1][j+1] - presum[i+1][j-l+1] + presum[i-l+1][j-l+1] > threshold:\n",
    "                    l -= 1\n",
    "                res = max(res, l)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n= len(mat),len(mat[0])\n",
    "        k = min(m,n)\n",
    "        # 数据预处理\n",
    "        g = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                g[i][j] = mat[i-1][j-1]+g[i-1][j]+g[i][j-1]-g[i-1][j-1]\n",
    "        # 面积\n",
    "        def get(x1,y1,x2,y2):\n",
    "            return g[x2][y2]+g[x1-1][y1-1]-g[x1-1][y2]-g[x2][y1-1]\n",
    "        \n",
    "        for l in range(k,0,-1):\n",
    "            # '正方形左上角'\n",
    "            for x1 in range(m-l+1):\n",
    "                for y1 in range(n-l+1):\n",
    "                    res = get(x1+1,y1+1,x1+l,y1+l)\n",
    "                    if res <= threshold:\n",
    "                        return l\n",
    "        return 0 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        _sum = [[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                _sum[i+1][j+1] = _sum[i+1][j]+_sum[i][j+1]-_sum[i][j]+mat[i][j]\n",
    "        lim = min(m,n)\n",
    "        def sum(row,col,l):\n",
    "\n",
    "            b = _sum[row+1][col+1]-_sum[row+1][col-l+1]-_sum[row+1-l][col+1]+_sum[row+1-l][col+1-l]\n",
    "            \n",
    "            return b\n",
    "        while lim>0:\n",
    "            row = m-1\n",
    "            while row-(lim-1)>=0:\n",
    "                col = n-1\n",
    "                while col-(lim-1)>=0:\n",
    "                    if sum(row,col,lim)<=threshold:return lim\n",
    "                    col-=1\n",
    "                row-=1\n",
    "            lim-=1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def getRect(x1, y1, x2, y2):\n",
    "            return P[x2][y2] - P[x1 - 1][y2] - P[x2][y1 - 1] + P[x1 - 1][y1 - 1]\n",
    "        \n",
    "        r, ans = min(m, n), 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                for c in range(ans + 1, r + 1):\n",
    "                    if i + c - 1 <= m and j + c - 1 <= n and getRect(i, j, i + c - 1, j + c - 1) <= threshold:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        # 元素和 小于等于阈值\n",
    "\n",
    "        # 预处理 构造前缀和\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i -  1][j - 1] + mat[i - 1][j - 1]\n",
    "        minlen = min(n, m)\n",
    "\n",
    "        for i in range(minlen, 0, -1):\n",
    "            for r in range(m - i + 1):\n",
    "                for c in range(n - i + 1):\n",
    "                    if dp[r + i][c + i] - dp[r][c + i] - dp[r + i][c] + dp[r][c] <= threshold:\n",
    "                        return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dp =[[0 for i in range(n + 1)] for j in range(m + 1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=mat[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]\n",
    "        def check(x:int)->bool:\n",
    "            for i in range(1,m+1):\n",
    "                for j in range(1,n+1):\n",
    "                    if i-x<0 or j-x<0:\n",
    "                        continue\n",
    "                    if dp[i][j]-dp[i-x][j]-dp[i][j-x]+dp[i-x][j-x]<=threshold:\n",
    "                        return True\n",
    "            return False\n",
    "        low,high=0,min(m,n)\n",
    "        while low<high:\n",
    "            mid=((high-low+1)>>1)+low\n",
    "            if check(mid):\n",
    "                low=mid\n",
    "            else:\n",
    "                high=mid-1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        s=[[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                s[i+1][j+1]=s[i][j+1]+s[i+1][j]+mat[i][j]-s[i][j]\n",
    "\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m-d+1):\n",
    "                for j in range(n-d+1):\n",
    "                    if s[i+d][j+d]+s[i][j]-s[i+d][j]-s[i][j+d]<=threshold:\n",
    "                        return d\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        qsum = []\n",
    "        for _ in range(m+1):\n",
    "            qsum.append([0]*(n+1))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                qsum[i+1][j+1] = mat[i][j] + qsum[i][j+1] + qsum[i+1][j] - qsum[i][j]\n",
    "        for d in range(min(m,n),0,-1):\n",
    "            for i in range(m-d+1):\n",
    "                for j in range(n-d+1):\n",
    "                    temp = qsum[i+d][j+d] - qsum[i][j+d] - qsum[i+d][j] + qsum[i][j]\n",
    "                \n",
    "                    if temp <= threshold:\n",
    "                        return d\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二维前缀和\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        s = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "        for i, col in enumerate(mat):\n",
    "            for j, v in enumerate(col):\n",
    "                s[i + 1][j + 1] = s[i][j + 1] + s[i + 1][j] - s[i][j] + v\n",
    "\n",
    "        def check(L: int) -> bool:\n",
    "            for i in range(L, n + 1):\n",
    "                for j in range(L, m + 1):\n",
    "                    if s[i][j] - s[i][j - L] - s[i - L][j] + s[i - L][j - L] <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "        lo, hi = 0, min(n, m)\n",
    "        while lo < hi:\n",
    "            mid = (lo + hi + 1) // 2\n",
    "            if check(mid):\n",
    "                lo = mid\n",
    "            else:\n",
    "                hi = mid - 1\n",
    "        return lo "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, grid: List[List[int]], threshold: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # 二维前缀和\n",
    "        preSum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        # 计算 preSum\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                preSum[i + 1][j + 1] = preSum[i][j + 1] + sum([grid[i][x] for x in range(j + 1)])\n",
    "            \n",
    "        # for i in range(m):\n",
    "        #     print(preSum[i])\n",
    "        \n",
    "        l, r = 1, min(m, n)\n",
    "        # 二分\n",
    "        while l <= r:\n",
    "            mid = l + (r - l) // 2\n",
    "            # print(mid)\n",
    "            gridSum = inf\n",
    "            # 对每个大小遍历？ \n",
    "            for i in range(m - mid + 1):\n",
    "                for j in range(n - mid + 1):\n",
    "                    ie = i + mid\n",
    "                    je = j + mid\n",
    "                    gridSum = min(gridSum, preSum[ie][je] + preSum[i][j] - preSum[i][je] - preSum[ie][j])\n",
    "                    # print(f'{i=}, {j=}, {ie=}, {je=}, {gridSum=}')\n",
    "            if gridSum <= threshold:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l - 1\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param mat:\n",
    "        :param threshold:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        # generate prefix sum\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        prefix = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            row_sum = 0\n",
    "            for j in range(1, n + 1):\n",
    "                row_sum += mat[i - 1][j - 1]\n",
    "                prefix[i][j] = prefix[i - 1][j] + row_sum\n",
    " \n",
    "        ans = 0\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                for k in range(ans, min(m - i + 1, n - j + 1)):\n",
    "                    if prefix[i + k][j + k] + prefix[i - 1][j - 1] - prefix[i - 1][j + k] - prefix[i + k][j - 1] <= threshold:\n",
    "                        ans = max(ans, k + 1)\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "a = Solution()\n",
    "print(a.maxSideLength(mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        k = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = [[0 for _ in range(n + 1)]]\n",
    "        for i in range(m):\n",
    "            tmp = [0]\n",
    "            sub.append(tmp)\n",
    "            for j in range(n):\n",
    "                tmp.append(mat[i][j] + sub[i + 1][j] + sub[i][j + 1] - sub[i][j])\n",
    "            \n",
    "        for idx_i in range(m, -1, -1):\n",
    "            i, j = idx_i, n\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                    ni -= 1\n",
    "                    nj -= 1\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "\n",
    "        for idx_j in range(n, -1, -1):\n",
    "            i, j = m, idx_j\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    # print(f\"i:{i} j:{j} ni:{ni} nj:{nj} sum:{sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj]}\")\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                    ni -= 1\n",
    "                    nj -= 1\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            \n",
    "        # for l in sub:\n",
    "        #     print(l)\n",
    "\n",
    "\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        ans = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        state = [[0 for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                state[i][j] = mat[i][j] + (state[i][j-1] if j > 0 else 0) + (state[i-1][j] if i > 0 else 0) - (state[i-1][j-1] if j > 0 and i > 0 else 0)\n",
    "                max_edge = min(i, j) + 1\n",
    "                if ans < max_edge:\n",
    "                    for k in range(max_edge, ans, -1):\n",
    "                        sq = state[i][j] - (state[i][j-k] if j >= k else 0) - (state[i-k][j] if i >= k else 0) + (state[i-k][j-k] if i >= k and j >= k else 0)\n",
    "                        if sq <= threshold:\n",
    "                            ans = k\n",
    "                            break\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        if not mat or not mat[0]:\n",
    "            return 0\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        \n",
    "        # 计算前缀和\n",
    "        prefix_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prefix_sum[i + 1][j + 1] = mat[i][j] + prefix_sum[i + 1][j] + prefix_sum[i][j + 1] - prefix_sum[i][j]\n",
    "\n",
    "        # 计算子矩阵的和\n",
    "        def get_sum(x1, y1, x2, y2):\n",
    "            return prefix_sum[x2 + 1][y2 + 1] - prefix_sum[x2 + 1][y1] - prefix_sum[x1][y2 + 1] + prefix_sum[x1][y1]\n",
    "\n",
    "        # 检查是否存在这样的正方形\n",
    "        def check(size):\n",
    "            for i in range(m - size + 1):\n",
    "                for j in range(n - size + 1):\n",
    "                    if get_sum(i, j, i + size - 1, j + size - 1) <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        # 二分查找最大边长\n",
    "        left, right, res = 0, min(m, n), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "\n",
    "        dp = [[0 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        flag = True\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                if mat[i-1][j-1] <= threshold:\n",
    "                    flag = False\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i-1][j-1]\n",
    "        if flag:\n",
    "            return 0\n",
    "        \n",
    "        ans = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                x, y = i - ans, j - ans\n",
    "                temp = ans\n",
    "                while  x >= 0 and y >= 0 and dp[i][j] - dp[x][j] - dp[i][y] + dp[x][y] <= threshold:\n",
    "                    ans = max(temp, ans)\n",
    "                    x -= 1\n",
    "                    y -= 1\n",
    "                    temp += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dp=[[0 for i in range(n+1)] for j in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                dp[i][j]=mat[i-1][j-1]+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]\n",
    "        def check(k:int)->bool:\n",
    "            for i in range(1,m+1):\n",
    "                for j in range(1,n+1):\n",
    "                    if i-k<0 or j-k<0:\n",
    "                        continue\n",
    "                    if dp[i][j]-dp[i-k][j]-dp[i][j-k]+dp[i-k][j-k]<=threshold:\n",
    "                        return True\n",
    "            return False\n",
    "        low,high=0,min(m,n)\n",
    "        while low<high:\n",
    "            mid=((high-low+1)>>1)+low\n",
    "            if check(mid):\n",
    "                low=mid\n",
    "            else:\n",
    "                high=mid-1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, mat: List[List[int]]):\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x\n",
    "        self.s = s\n",
    "\n",
    "    def query(self, x1: int, y1: int, x2: int, y2: int) -> int:\n",
    "        return self.s[x2 + 1][y2 + 1] - self.s[x2 + 1][y1] - self.s[x1][y2 + 1] + self.s[x1][y1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        ms = MatrixSum(mat)\n",
    "\n",
    "        def check(w: int) -> bool:\n",
    "            for x1 in range(0, n - w + 1):\n",
    "                for y1 in range(0, m - w + 1):\n",
    "                    x2, y2 = x1 + w - 1, y1 + w - 1\n",
    "                    if ms.query(x1, y1, x2, y2) <= threshold:\n",
    "                        return True\n",
    "            return False\n",
    "\n",
    "        l, r = 0, min(n, m) + 1\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid\n",
    "        return l - 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        presum = [[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i].append(presum[i][-1]+mat[i][j])\n",
    "\n",
    "        def check(x):\n",
    "            for k in range(m-x+1):\n",
    "                for j in range(n-x+1):\n",
    "                    res = 0\n",
    "                    for i in range(k,k+x):\n",
    "                        res += presum[i][j+x] - presum[i][j]\n",
    "                    if(res <= threshold):\n",
    "                        return True \n",
    "            return False\n",
    "        left, right = 0, min(m,n)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        def buildAreas(mat):\n",
    "            m, n = len(mat), len(mat[0])\n",
    "            areas = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    areas[i+1][j+1] = areas[i+1][j] + areas[i][j+1] + mat[i][j] - areas[i][j]\n",
    "            return areas\n",
    "        \n",
    "        def calcSquareArea(i, j, borderLen, areas):\n",
    "            if borderLen == 0:\n",
    "                return 0\n",
    "            i2, j2 = i - borderLen, j - borderLen\n",
    "            return areas[i+1][j+1] - areas[i+1][j2+1] - areas[i2+1][j+1] + areas[i2+1][j2+1]\n",
    "\n",
    "        areas = buildAreas(mat)\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        borderLen = m if m < n else n\n",
    "        ans = 0\n",
    "        while borderLen > 0:\n",
    "            for i in range(m - 1, borderLen - 2, -1):\n",
    "                for j in range(n - 1, borderLen - 2, -1):\n",
    "                    squareArea = calcSquareArea(i, j, borderLen, areas)\n",
    "                    if squareArea <= threshold:\n",
    "                        ans = max(ans, borderLen)\n",
    "            borderLen -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        presum = [[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i].append(presum[i][-1]+mat[i][j])\n",
    "\n",
    "        def check(x):\n",
    "            for k in range(m-x+1):\n",
    "                for j in range(n-x+1):\n",
    "                    res = 0\n",
    "                    for i in range(k,k+x):\n",
    "                        res += presum[i][j+x] - presum[i][j]\n",
    "                    if(res <= threshold):\n",
    "                        return True \n",
    "            return False\n",
    "        left, right = 0, min(m,n)\n",
    "        while(left <= right):\n",
    "            mid = (left+right)//2\n",
    "            if(check(mid)):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        h = len(mat)\n",
    "        w = len(mat[0])\n",
    "\n",
    "        presum = [[0 for i in range(w + 1)] for i in range(h + 1)]\n",
    "        # presum[0][0] = mat[0][0]\n",
    "        # for i in range(1, h):\n",
    "        #     presum[i][0] = presum[i - 1][0] + mat[i][0]\n",
    "        # for j in range(1, w):\n",
    "        #     presum[0][j] = presum[0][j - 1] + mat[0][j]\n",
    "        for i in range(1, h + 1):\n",
    "            for j in range(1, w + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "\n",
    "        ans = 0\n",
    "        r = min(h, w)\n",
    "        for i in range(1, h + 1):\n",
    "            for j in range(1, w + 1):\n",
    "                for c in range(ans + 1, r + 1):\n",
    "                    if i + c - 1 > h or j + c - 1 > w:\n",
    "                        continue\n",
    "                    s = presum[i + c - 1][j + c - 1] - presum[i + c - 1][j - 1] - presum[i - 1][j + c - 1] + presum[i - 1][j - 1]\n",
    "                    if s <= threshold:\n",
    "                        ans = max(ans, c)\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre_sum, self.threshold = None, None\n",
    "\n",
    "    @staticmethod\n",
    "    def get_pre_sum(mat: List[List[int]]) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pre_sum = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        # init\n",
    "        pre_sum[0][0] = mat[0][0]\n",
    "        for j in range(1, n):\n",
    "            pre_sum[0][j] = pre_sum[0][j - 1] + mat[0][j]\n",
    "        for i in range(1, m):\n",
    "            pre_sum[i][0] = pre_sum[i - 1][0] + mat[i][0]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] - pre_sum[i - 1][j - 1] + mat[i][j]\n",
    "        return pre_sum\n",
    "\n",
    "    def valid_check(self, edge_len: int) -> int:\n",
    "        if edge_len == 0:\n",
    "            return False\n",
    "        m, n = len(self.pre_sum), len(self.pre_sum[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                nex_i, nex_j = i + edge_len - 1, j + edge_len - 1\n",
    "\n",
    "                if not (0 <= nex_i < m and 0 <= nex_j < n):\n",
    "                    continue\n",
    "\n",
    "                part_sum1 = self.pre_sum[i - 1][nex_j] if i >= 1 else 0\n",
    "                part_sum2 = self.pre_sum[nex_i][j - 1] if j >= 1 else 0\n",
    "                part_sum3 = self.pre_sum[i - 1][j - 1] if i >= 1 and j >= 1 else 0\n",
    "                square_sum = self.pre_sum[nex_i][nex_j] - part_sum1 - part_sum2 + part_sum3\n",
    "                if square_sum <= self.threshold:\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        self.pre_sum = self.get_pre_sum(mat)\n",
    "        self.threshold = threshold\n",
    "\n",
    "        left, right = 0, min(len(mat), len(mat[0]))\n",
    "        while left < right:\n",
    "            middle = left + (right - left) // 2 + 1\n",
    "            if self.valid_check(middle):\n",
    "                left = middle\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        h = len(mat)\n",
    "        w = len(mat[0])\n",
    "\n",
    "        presum = [[0 for i in range(w + 1)] for i in range(h + 1)]\n",
    "        # presum[0][0] = mat[0][0]\n",
    "        # for i in range(1, h):\n",
    "        #     presum[i][0] = presum[i - 1][0] + mat[i][0]\n",
    "        # for j in range(1, w):\n",
    "        #     presum[0][j] = presum[0][j - 1] + mat[0][j]\n",
    "        for i in range(1, h + 1):\n",
    "            for j in range(1, w + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "\n",
    "        ans = 0\n",
    "        r = min(h, w)\n",
    "        for i in range(1, h + 1):\n",
    "            for j in range(1, w + 1):\n",
    "                for c in range(ans + 1, r + 1):\n",
    "                    if i + c - 1 > h or j + c - 1 > w:\n",
    "                        continue\n",
    "                    s = presum[i + c - 1][j + c - 1] - presum[i + c - 1][j - 1] - presum[i - 1][j + c - 1] + presum[i - 1][j - 1]\n",
    "                    if s <= threshold:\n",
    "                        # ans = max(ans, c)\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        k = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = [[0 for _ in range(n + 1)]]\n",
    "        for i in range(m):\n",
    "            tmp = [0]\n",
    "            sub.append(tmp)\n",
    "            for j in range(n):\n",
    "                tmp.append(mat[i][j] + sub[i + 1][j] + sub[i][j + 1] - sub[i][j])\n",
    "            \n",
    "        for idx_i in range(m, -1, -1):\n",
    "            i, j = idx_i, n\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                        ni -= 1\n",
    "                        nj -= 1\n",
    "                    else:\n",
    "                        break   \n",
    "                i -= 1\n",
    "                j -= 1\n",
    "\n",
    "        for idx_j in range(n, -1, -1):\n",
    "            i, j = m, idx_j\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    # print(f\"i:{i} j:{j} ni:{ni} nj:{nj} sum:{sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj]}\")\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                        ni -= 1\n",
    "                        nj -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "            \n",
    "        # for l in sub:\n",
    "        #     print(l)\n",
    "\n",
    "\n",
    "        return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSideLength(self, mat: List[List[int]], threshold: int) -> int:\n",
    "        k = 0\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = [[0 for _ in range(n + 1)]]\n",
    "        for i in range(m):\n",
    "            tmp = [0]\n",
    "            sub.append(tmp)\n",
    "            for j in range(n):\n",
    "                tmp.append(mat[i][j] + sub[i + 1][j] + sub[i][j + 1] - sub[i][j])\n",
    "            \n",
    "        for idx_i in range(m, -1, -1):\n",
    "            i, j = idx_i, n\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                        ni -= 1\n",
    "                        nj -= 1\n",
    "                    else:\n",
    "                        break   \n",
    "                i -= 1\n",
    "                j -= 1\n",
    "\n",
    "        for idx_j in range(n, -1, -1):\n",
    "            i, j = m, idx_j\n",
    "            \n",
    "            while i > 0 and j > 0:\n",
    "                ni, nj = i - k, j - k\n",
    "                while ni >= 0 and nj >= 0:\n",
    "                    if sub[i][j] + sub[ni][nj] - sub[ni][j] - sub[i][nj] <= threshold:\n",
    "                        k = max(i - ni, k)\n",
    "                        ni -= 1\n",
    "                        nj -= 1\n",
    "                    else:\n",
    "                        break\n",
    "                i -= 1\n",
    "                j -= 1\n",
    "\n",
    "        return k"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
